/*
请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

请你完成 FrontMiddleBack 类：
+ FrontMiddleBack() 初始化队列。
+ void pushFront(int val) 将 val 添加到队列的 最前面 。
+ void pushMiddle(int val) 将 val 添加到队列的 正中间 。
+ void pushBack(int val) 将 val 添加到队里的 最后面 。
+ int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
+ int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
+ int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：
将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。


输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释：
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] （队列为空）

涉及中间操作时 如果是双数 则取前面一个

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-front-middle-back-queue
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */

// 前端能进能出 后端能进能出 中间也能进能出

/*
 * @lc app=leetcode.cn id=1670 lang=javascript
 *
 * [1670] 设计前中后队列
 */

// @lc code=start

//<editor-fold desc="双向链表节点">
var Node = function (val) {
  this.val = val;
  this.pre = null;
  this.next = null;
}
// 节点前面插入新节点 p
Node.prototype.insert_pre = function (p) {
  p.next = this;
  p.pre = this.pre;
  this.pre && (this.pre.next = p); // this指虚拟尾
  this.pre = p;
}
// 节点后面插入新节点 p
Node.prototype.insert_next = function (p) {
  p.pre = this;
  p.next = this.next;
  this.next && (this.next.pre = p);  // this指虚拟头
  this.next = p;
}
Node.prototype.erase = function () {
  this.next && (this.next.pre = this.pre);
  this.pre && (this.pre.next = this.next);
}
//</editor-fold>

//<editor-fold desc="双向链表实双端队列">
var deQueue = function () {
  this.cnt = 0;
  this.head = new Node(-1); // 头虚拟节点
  this.tail = new Node(-1); // 尾虚拟结点
  this.head.next = this.tail;
  this.tail.pre = this.head;
}
deQueue.prototype.push = function (value) {
  this.tail.insert_pre(new Node(value));
  this.cnt += 1;
}
deQueue.prototype.unshift = function (value) {
  this.head.insert_next(new Node(value));
  this.cnt += 1;
}
deQueue.prototype.pop = function () {
  if (this.cnt <= 0) return undefined;
  let ret = this.tail.pre.val;
  this.tail.pre.erase();
  this.cnt--;
  return ret;
}
deQueue.prototype.shift = function () {
  if (this.cnt <= 0) return undefined;
  let ret = this.head.next.val;
  this.head.next.erase();
  this.cnt--;
  return ret;
}
deQueue.prototype.front = function () {
  return this.head.next.val;
}
deQueue.prototype.back = function () {
  return this.tail.pre.val;
}
deQueue.prototype.length = function () {
  return this.cnt;
}
//</editor-fold>


/**
 * 思路：用两个双端队列来实现
 * 下面解法借用了数组的api, 应该自己封装双端队列。
 */
var FrontMiddleBackQueue = function() {
  this.leftQueue = new deQueue(); // 为什么用链表? 如果是数组的话 比如从头unshift 头指针往左移动 那总是出界的(下标会变为负数) 但链表就没这个问题 (并且数组我们也没法在长度不定的情况下绕圈)
  this.rightQueue = new deQueue(); // 奇数时右侧数组大1(比左边多一个)
  this.count = 0;
};

/**
 * @param {number} val
 * @return {void}
 */
// 调节两个对列的元素
FrontMiddleBackQueue.prototype.ava = function() {
  // 右侧个数比左侧多，且多于1个
  while(this.rightQueue.length() - this.leftQueue.length() > 1){
    this.leftQueue.push(this.rightQueue.shift())
  }
  // 左侧比右侧多
  while(this.rightQueue.length() - this.leftQueue.length() < 0){
    this.rightQueue.unshift(this.leftQueue.pop())
  }
};
FrontMiddleBackQueue.prototype.isEmpty = function() {
  return this.count === 0;
};

FrontMiddleBackQueue.prototype.pushFront = function(val) {
  this.leftQueue.unshift(val);
  this.count++;
  this.ava(); //把左侧多的放到右侧去 平衡
  return null;
};

/**
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushMiddle = function(val) {
  this.leftQueue.push(val)
  this.count++;
  this.ava();
  return null;
};

/**
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushBack = function(val) {
  this.rightQueue.push(val);
  this.count++;
  this.ava();
  return null;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popFront = function() {
  if(this.isEmpty()) return -1;
  let value = ''
  // 优先弹出左侧队列的元素
  if(this.leftQueue.length()){
    value = this.leftQueue.shift();
  } else {
    value = this.rightQueue.shift();
  }
  this.count--;
  this.ava();
  return value;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popMiddle = function() {
  if(this.isEmpty()) return -1;
  let value = ''
  // 如果是偶数个，弹出中间偏左的元素
  if(this.rightQueue.length() === this.leftQueue.length()){
    value = this.leftQueue.pop();
  } else { // 否则中间元素为右队列第一个 (我们之前设置了 奇数个的时候 多的那个会放在右侧)
    value = this.rightQueue.shift();
  }
  this.count--;
  this.ava();
  return value;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popBack = function() {
  if(this.isEmpty()) return -1;
  let value = this.rightQueue.pop();
  this.count--;
  this.ava();
  return value;
};


/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * var obj = new FrontMiddleBackQueue()
 * obj.pushFront(val)
 * obj.pushMiddle(val)
 * obj.pushBack(val)
 * var param_4 = obj.popFront()
 * var param_5 = obj.popMiddle()
 * var param_6 = obj.popBack()
 */
// @lc code=end

